/*
题目: 安排电影院座位
如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。

给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，researvedSeats[i]=[3,8] ，它表示第 3 行第 8 个座位被预约了。

请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座位，但是如果你可以将 4 人家庭拆成过道两边各坐 2 人，这样子是允许的。

https://leetcode.cn/problems/cinema-seat-allocation
 */
public class MaxNumberOfFamilies {
    public int maxNumberOfFamilies(int n, int[][] r) {
        // 用 位运算 记录每一排的情况, 1 表示有预定, 0 表示是空位
        // 其中第一列 和 最后一列对结果没有影响, 其他位有一个预定, 就最多只能坐一个家庭

        // Arrays.sort(r, new Comparator<int[]> () {
        //     // 按照行排序,  实际上不用排序
        //     public int compare(int[] o1, int[] o2) {
        //         if (o1[0] != o2[0]) {
        //             return o1[0] - o2[0];
        //         }
        //         return o1[1] - o2[1];
        //     }
        // });
        int row = r.length;

        // 行数, 座位情况
        Map<Integer, Integer> map = new HashMap<> ();
        for (int[] cur : r) {
            if (cur[1] == 1 || cur[1] == 10)    continue ; // 第一列 和 最后一列 对结果没有影响

            int move = 1 << (cur[1] - 2);  // 先计算出移位
            map.put(cur[0], map.getOrDefault(cur[0], 0) | move); // 取出那一行的座位情况, 并更新, 再覆盖
        }
        // int curRow = 1;
        // int bit = 0b0;
        // for (int i = 0; i < row; i ++) {
        //     if (r[i][1] == 1 || r[i][1] == 10)  continue ;

        //     if (r[i][0] == curRow) {
        //         bit |= (1 << (r[i][1] - 2));
        //     } else {
        //         curRow = r[i][0];
        //         bit = 0;
        //         bit |= (1 << (r[i][1] - 2));
        //     }
        //     map.put(curRow, bit);
        // }

        int src = (n - map.size()) * 2; // 没有记录过的就是可以做满两个家庭的
        int leftBit = 0b00001111;  // 左边 4 个位置没有人, 如果座位情况 和 leftBit 按位或的结果没有变化, 说明符合 4 个 0 的位置都是0
        int midBit = 0b11000011;   // 中间 4 个位置没有人
        int rightBit = 0b11110000; // 右边 4 个位置没有人
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int cur = entry.getValue();
            // 其中一个满足, 就能安排一个座位
            if ((cur | leftBit) == leftBit || (cur | midBit) == midBit || (cur | rightBit) == rightBit)
                src ++;
        }
        return src;
    }
}
